import java.util.*;

/**
 * 正则表达式(a|b)*(aa|bb)(a|b)*的自动机处理程序
 * 包含NFA构造、NFA确定化、DFA最小化以及识别字符串功能
 */
public class RegexAutomata {
    // 定义字母表
    private static final char[] ALPHABET = {'a', 'b'};

    // 定义ε转换的特殊字符
    private static final char EPSILON = 'ε';
    
    // NFA的转换矩阵，使用列表存储三元组(起始状态,输入字符,目标状态)
    private List<Transition> nfaTransitions = new ArrayList<>();
    // NFA的状态集合
    private Set<Integer> nfaStates = new HashSet<>();
    // NFA的开始状态
    private int nfaStartState;
    // NFA的接受状态集合
    private Set<Integer> nfaAcceptStates = new HashSet<>();
    
    // DFA的转换矩阵，使用Map嵌套结构表示
    private Map<Set<Integer>, Map<Character, Set<Integer>>> dfaTransitions = new HashMap<>();
    // DFA的状态集合（每个状态是NFA状态的一个子集）
    private Set<Set<Integer>> dfaStates = new HashSet<>();
    // DFA的开始状态
    private Set<Integer> dfaStartState;
    // DFA的接受状态集合
    private Set<Set<Integer>> dfaAcceptStates = new HashSet<>();
    
    // 最小化DFA的转换矩阵
    private Map<Integer, Map<Character, Integer>> minDfaTransitions = new HashMap<>();
    // 最小化DFA的状态集合
    private Set<Integer> minDfaStates = new HashSet<>();
    // 最小化DFA的开始状态
    private int minDfaStartState;
    // 最小化DFA的接受状态集合
    private Set<Integer> minDfaAcceptStates = new HashSet<>();
    
    /**
     * 三元组类，表示从一个状态通过一个输入字符到另一个状态的转换
     */
    static class Transition {
        int fromState;
        char inputChar;
        int toState;
        
        public Transition(int fromState, char inputChar, int toState) {
            this.fromState = fromState;
            this.inputChar = inputChar;
            this.toState = toState;
        }
        
        @Override
        public String toString() {
            return "(" + fromState + ", " + inputChar + ", " + toState + ")";
        }
    }
    
    /**
     * 手动构造NFA
     * 正则表达式(a|b)*(aa|bb)(a|b)*
     */
    public void constructNFA() {
        /*
         * 构造NFA如下：
         * 状态0: 开始状态
         * 状态1-8: 中间状态
         * 状态9: 接受状态
         * 
         * 正则表达式(a|b)*(aa|bb)(a|b)*的NFA结构:
         * (a|b)*部分: 状态0-2
         * (aa|bb)部分: 状态3-6
         * (a|b)*部分: 状态7-9
         */
        
        // 添加NFA状态
        for (int i = 0; i <= 9; i++) {
            nfaStates.add(i);
        }
        
        // 设置开始和接受状态
        nfaStartState = 0;
        nfaAcceptStates.add(9);
        
        // 添加转换关系
        // (a|b)*部分
        addNFATransition(0, EPSILON, 1);  // 开始到(a|b)*循环
        addNFATransition(0, EPSILON, 3);  // 开始到(aa|bb)部分
        addNFATransition(1, 'a', 2);      // a转换
        addNFATransition(1, 'b', 2);      // b转换
        addNFATransition(2, EPSILON, 1);  // 返回循环开始
        addNFATransition(2, EPSILON, 3);  // 进入(aa|bb)部分
        
        // (aa|bb)部分
        addNFATransition(3, EPSILON, 4);  // aa路径
        addNFATransition(3, EPSILON, 6);  // bb路径
        addNFATransition(4, 'a', 5);      // 第一个a
        addNFATransition(5, 'a', 7);      // 第二个a
        addNFATransition(6, 'b', 7);      // 第一个b
        addNFATransition(7, 'b', 8);      // 第二个b或进入最后部分
        
        // (a|b)*部分
        addNFATransition(8, EPSILON, 9);  // 直接到接受状态
        addNFATransition(8, EPSILON, 7);  // 继续循环
        addNFATransition(7, 'a', 8);      // a转换
        addNFATransition(7, 'b', 8);      // b转换
    }
    
    /**
     * 添加NFA转换
     * @param fromState 起始状态
     * @param inputChar 输入字符
     * @param toState 目标状态
     */
    public void addNFATransition(int fromState, char inputChar, int toState) {
        nfaTransitions.add(new Transition(fromState, inputChar, toState));
    }
    
    /**
     * 打印NFA的状态矩阵
     */
    public void printNFA() {
        System.out.println("NFA状态矩阵:");
        System.out.println("开始状态: " + nfaStartState);
        System.out.println("接受状态: " + nfaAcceptStates);
        System.out.println("转换关系:");
        
        // 按起始状态排序后打印
        nfaTransitions.sort(Comparator.comparingInt(t -> t.fromState));
        for (Transition t : nfaTransitions) {
            System.out.println(t);
        }
        System.out.println();
    }
    
    /**
     * 计算NFA状态集的ε闭包
     * @param states NFA状态集
     * @return ε闭包
     */
    private Set<Integer> epsilonClosure(Set<Integer> states) {
        Stack<Integer> stack = new Stack<>();
        Set<Integer> closure = new HashSet<>(states);
        
        // 将初始状态集压入栈
        for (int state : states) {
            stack.push(state);
        }
        
        // 遍历栈处理ε转换
        while (!stack.isEmpty()) {
            int state = stack.pop();
            
            // 查找所有从当前状态通过ε可达的状态
            for (Transition t : nfaTransitions) {
                if (t.fromState == state && t.inputChar == EPSILON && !closure.contains(t.toState)) {
                    closure.add(t.toState);
                    stack.push(t.toState);
                }
            }
        }
        
        return closure;
    }
    
    /**
     * 计算NFA状态集通过输入字符可达的状态集
     * @param states NFA状态集
     * @param inputChar 输入字符
     * @return 可达状态集
     */
    private Set<Integer> move(Set<Integer> states, char inputChar) {
        Set<Integer> reachableStates = new HashSet<>();
        
        // 查找所有从当前状态集通过输入字符可达的状态
        for (int state : states) {
            for (Transition t : nfaTransitions) {
                if (t.fromState == state && t.inputChar == inputChar) {
                    reachableStates.add(t.toState);
                }
            }
        }
        
        return reachableStates;
    }
    
    /**
     * NFA转DFA
     * 使用子集构造法
     */
    public void convertNFAtoDFA() {
        // 计算开始状态的ε闭包作为DFA的开始状态
        Set<Integer> startStateSet = new HashSet<>();
        startStateSet.add(nfaStartState);
        dfaStartState = epsilonClosure(startStateSet);
        
        // 待处理的DFA状态队列
        Queue<Set<Integer>> workList = new LinkedList<>();
        workList.add(dfaStartState);
        dfaStates.add(dfaStartState);
        
        // 处理队列中的每个状态
        while (!workList.isEmpty()) {
            Set<Integer> currentState = workList.poll();
            
            // 对字母表中的每个字符，计算转换后的新状态
            for (char c : ALPHABET) {
                // 计算从当前状态通过字符c可达的状态集的ε闭包
                Set<Integer> nextState = epsilonClosure(move(currentState, c));
                
                if (!nextState.isEmpty()) {
                    // 添加新状态（如果尚未存在）
                    if (!dfaStates.contains(nextState)) {
                        dfaStates.add(nextState);
                        workList.add(nextState);
                    }
                    
                    // 添加转换关系
                    dfaTransitions.computeIfAbsent(currentState, k -> new HashMap<>()).put(c, nextState);
                }
            }
        }
        
        // 确定DFA的接受状态
        for (Set<Integer> state : dfaStates) {
            // 如果DFA状态包含NFA的任一接受状态，则它是DFA的接受状态
            for (int acceptState : nfaAcceptStates) {
                if (state.contains(acceptState)) {
                    dfaAcceptStates.add(state);
                    break;
                }
            }
        }
    }
    
    /**
     * 打印DFA的状态矩阵
     */
    public void printDFA() {
        System.out.println("DFA状态矩阵:");
        System.out.println("开始状态: " + dfaStartState);
        System.out.println("接受状态: " + dfaAcceptStates);
        System.out.println("转换关系:");
        
        // 给DFA状态分配编号，便于显示
        Map<Set<Integer>, Integer> stateMapping = new HashMap<>();
        int stateCounter = 0;
        for (Set<Integer> state : dfaStates) {
            stateMapping.put(state, stateCounter++);
        }
        
        // 打印转换关系
        for (Map.Entry<Set<Integer>, Map<Character, Set<Integer>>> entry : dfaTransitions.entrySet()) {
            Set<Integer> fromState = entry.getKey();
            Map<Character, Set<Integer>> transitions = entry.getValue();
            
            for (Map.Entry<Character, Set<Integer>> transition : transitions.entrySet()) {
                char inputChar = transition.getKey();
                Set<Integer> toState = transition.getValue();
                
                System.out.println("(" + stateMapping.get(fromState) + ", " + 
                                  inputChar + ", " + stateMapping.get(toState) + ")");
            }
        }
        System.out.println();
    }
    
    /**
     * 最小化DFA
     * 使用划分法
     */
    public void minimizeDFA() {
        // 初始划分：接受状态和非接受状态
        List<Set<Set<Integer>>> partitions = new ArrayList<>();
        Set<Set<Integer>> acceptingStates = new HashSet<>(dfaAcceptStates);
        Set<Set<Integer>> nonAcceptingStates = new HashSet<>(dfaStates);
        nonAcceptingStates.removeAll(acceptingStates);
        
        if (!acceptingStates.isEmpty()) {
            partitions.add(acceptingStates);
        }
        if (!nonAcceptingStates.isEmpty()) {
            partitions.add(nonAcceptingStates);
        }
        
        // 划分，直到不能再划分
        boolean changed = true;
        while (changed) {
            changed = false;
            
            List<Set<Set<Integer>>> newPartitions = new ArrayList<>();
            
            // 对每个划分进行细分
            for (Set<Set<Integer>> partition : partitions) {
                if (partition.size() <= 1) {
                    newPartitions.add(partition);
                    continue;
                }
                
                // 选取一个状态作为代表
                Set<Integer> representative = partition.iterator().next();
                
                // 根据转换关系细分当前划分
                Map<String, Set<Set<Integer>>> subPartitions = new HashMap<>();
                
                for (Set<Integer> state : partition) {
                    StringBuilder transitionSignature = new StringBuilder();
                    
                    // 构建状态的转换特征
                    for (char c : ALPHABET) {
                        Set<Integer> nextState = dfaTransitions.getOrDefault(state, Collections.emptyMap())
                                                             .getOrDefault(c, Collections.emptySet());
                        
                        // 确定nextState所在的划分
                        int partitionIndex = -1;
                        for (int i = 0; i < partitions.size(); i++) {
                            if (partitions.get(i).contains(nextState)) {
                                partitionIndex = i;
                                break;
                            }
                        }
                        
                        transitionSignature.append(c).append("->").append(partitionIndex).append(",");
                    }
                    
                    // 将状态加入对应的子划分
                    subPartitions.computeIfAbsent(transitionSignature.toString(), k -> new HashSet<>()).add(state);
                }
                
                // 添加细分后的子划分
                for (Set<Set<Integer>> subPartition : subPartitions.values()) {
                    newPartitions.add(subPartition);
                }
                
                // 如果原划分被细分，则标记为发生变化
                if (subPartitions.size() > 1) {
                    changed = true;
                }
            }
            
            partitions = newPartitions;
        }
        
        // 根据最终划分构建最小化DFA
        Map<Set<Integer>, Integer> minStateMapping = new HashMap<>();
        int stateCounter = 0;
        
        // 为每个划分分配一个状态编号
        for (Set<Set<Integer>> partition : partitions) {
            for (Set<Integer> state : partition) {
                minStateMapping.put(state, stateCounter);
            }
            minDfaStates.add(stateCounter);
            stateCounter++;
        }
        
        // 设置最小化DFA的开始状态
        minDfaStartState = minStateMapping.get(dfaStartState);
        
        // 设置最小化DFA的接受状态
        for (Set<Integer> acceptState : dfaAcceptStates) {
            minDfaAcceptStates.add(minStateMapping.get(acceptState));
        }
        
        // 构建最小化DFA的转换关系
        for (Map.Entry<Set<Integer>, Map<Character, Set<Integer>>> entry : dfaTransitions.entrySet()) {
            Set<Integer> fromState = entry.getKey();
            Map<Character, Set<Integer>> transitions = entry.getValue();
            
            int minFromState = minStateMapping.get(fromState);
            
            for (Map.Entry<Character, Set<Integer>> transition : transitions.entrySet()) {
                char inputChar = transition.getKey();
                Set<Integer> toState = transition.getValue();
                int minToState = minStateMapping.get(toState);
                
                minDfaTransitions.computeIfAbsent(minFromState, k -> new HashMap<>()).put(inputChar, minToState);
            }
        }
    }
    
    /**
     * 打印最小化DFA的状态矩阵
     */
    public void printMinDFA() {
        System.out.println("最小化DFA状态矩阵:");
        System.out.println("开始状态: " + minDfaStartState);
        System.out.println("接受状态: " + minDfaAcceptStates);
        System.out.println("转换关系:");
        
        // 打印转换关系
        for (Map.Entry<Integer, Map<Character, Integer>> entry : minDfaTransitions.entrySet()) {
            int fromState = entry.getKey();
            Map<Character, Integer> transitions = entry.getValue();
            
            for (Map.Entry<Character, Integer> transition : transitions.entrySet()) {
                char inputChar = transition.getKey();
                int toState = transition.getValue();
                
                System.out.println("(" + fromState + ", " + inputChar + ", " + toState + ")");
            }
        }
        System.out.println();
    }
    
    /**
     * 使用最小化DFA识别输入字符串
     * @param input 输入字符串
     * @return 是否被接受
     */
    public boolean recognizeString(String input) {
        // 从开始状态出发
        int currentState = minDfaStartState;
        
        // 逐个处理输入字符
        for (char c : input.toCharArray()) {
            // 检查输入字符是否在字母表中
            if (c != 'a' && c != 'b') {
                System.out.println("非法输入字符: " + c);
                return false;
            }
            
            // 获取下一个状态
            Map<Character, Integer> transitions = minDfaTransitions.get(currentState);
            if (transitions == null || !transitions.containsKey(c)) {
                System.out.println("在状态 " + currentState + " 没有针对输入 " + c + " 的转换");
                return false;
            }
            
            currentState = transitions.get(c);
        }
        
        // 检查最终状态是否是接受状态
        return minDfaAcceptStates.contains(currentState);
    }
    
    public static void main(String[] args) {
        RegexAutomata automata = new RegexAutomata();
        
        // 步骤1：构造NFA
        System.out.println("步骤1：构造正则表达式(a|b)*(aa|bb)(a|b)*的NFA");
        automata.constructNFA();
        automata.printNFA();
        
        // 步骤2：NFA确定化为DFA
        System.out.println("步骤2：将NFA确定化为DFA");
        automata.convertNFAtoDFA();
        automata.printDFA();
        
        // 步骤3：DFA最小化
        System.out.println("步骤3：DFA最小化");
        automata.minimizeDFA();
        automata.printMinDFA();
        
        // 步骤4：使用最小化DFA识别输入字符串
        System.out.println("步骤4：使用最小化DFA识别输入字符串");
        Scanner scanner = new Scanner(System.in);
        
        while (true) {
            System.out.print("请输入要测试的字符串（仅包含a和b，输入exit退出）: ");
            String input = scanner.nextLine();
            
            if (input.equalsIgnoreCase("exit")) {
                break;
            }
            
            boolean accepted = automata.recognizeString(input);
            
            if (accepted) {
                System.out.println("接受：'" + input + "' 符合正则表达式(a|b)*(aa|bb)(a|b)*");
            } else {
                System.out.println("拒绝：'" + input + "' 不符合正则表达式(a|b)*(aa|bb)(a|b)*");
            }
            System.out.println();
        }
        
        scanner.close();
    }
}